home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 May: Tool Chest / Developer CD Series May 1996 (Tool Chest) (Apple Computer) (1996).iso / Tool Chest / Development Tools & Languages / Dylan Related / Marlais / Marlais 0.5.9-portable sources / deque.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-15  |  8.3 KB  |  354 lines  |  [TEXT/ttxt]
  1. /*
  2.  
  3.    deque.c 
  4.  
  5.    This software is free software; you can redistribute it and/or
  6.    modify it under the terms of the GNU Library General Public
  7.    License as published by the Free Software Foundation; either
  8.    version 2 of the License, or (at your option) any later version.
  9.  
  10.    This software is distributed in the hope that it will be useful,
  11.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13.    Library General Public License for more details.
  14.  
  15.    You should have received a copy of the GNU Library General Public
  16.    License along with this software; if not, write to the Free
  17.    Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  
  19.    Original copyright notice follows:
  20.  
  21.    Copyright, 1993, Brent Benson.  All Rights Reserved.
  22.    0.4 & 0.5 Revisions Copyright 1994, Joseph N. Wilson.  All Rights Reserved.
  23.  
  24.    Permission to use, copy, and modify this software and its
  25.    documentation is hereby granted only under the following terms and
  26.    conditions.  Both the above copyright notice and this permission
  27.    notice must appear in all copies of the software, derivative works
  28.    or modified version, and both notices must appear in supporting
  29.    documentation.  Users of this software agree to the terms and
  30.    conditions set forth in this notice.
  31.  
  32.  */
  33.  
  34. #include "deque.h"
  35.  
  36. #include "collection.h"
  37. #include "error.h"
  38. #include "list.h"
  39. #include "prim.h"
  40. #include "symbol.h"
  41.  
  42. /* primitives */
  43.  
  44. static Object push (Object d, Object new);
  45. static Object pop (Object d);
  46. static Object push_last (Object d, Object new);
  47. static Object pop_last (Object d);
  48. static Object deque_first (Object d, Object default_ob);
  49. static Object deque_last (Object d, Object default_ob);
  50. static Object deque_element (Object d, Object i, Object default_ob);
  51. static Object deque_element_setter (Object d, Object i, Object new);
  52. static Object deque_initial_state (Object d);
  53. static Object deque_next_state (Object d, Object s);
  54. static Object deque_final_state (Object d);
  55. static Object deque_previous_state (Object d, Object s);
  56. static Object deque_current_element (Object d, Object s);
  57. static Object deque_current_element_setter (Object d,
  58.                         Object s,
  59.                         Object new_value);
  60.  
  61. static struct primitive deque_prims[] =
  62. {
  63.     {"%push", prim_2, push},
  64.     {"%pop", prim_1, pop},
  65.     {"%push-last", prim_2, push_last},
  66.     {"%pop-last", prim_1, pop_last},
  67.     {"%deque-first", prim_2, deque_first},
  68.     {"%deque-last", prim_2, deque_last},
  69.     {"%deque-element", prim_3, deque_element},
  70.     {"%deque-element-setter", prim_3, deque_element_setter},
  71.     {"%deque-initial-state", prim_1, deque_initial_state},
  72.     {"%deque-next-state", prim_2, deque_next_state},
  73.     {"%deque-final-state", prim_1, deque_final_state},
  74.     {"%deque-previous-state", prim_2, deque_previous_state},
  75.     {"%deque-current-element", prim_2, deque_current_element},
  76.     {"%deque-current-element-setter", prim_3, deque_current_element_setter},
  77. };
  78.  
  79. void
  80. init_deque_prims (void)
  81. {
  82.     int num;
  83.  
  84.     num = sizeof (deque_prims) / sizeof (struct primitive);
  85.  
  86.     init_prims (num, deque_prims);
  87. }
  88.  
  89. Object
  90. make_deque (void)
  91. {
  92.     Object obj;
  93.  
  94.     obj = allocate_object (sizeof (struct deque));
  95.  
  96.     DEQUETYPE (obj) = Deque;
  97.     DEQUEFIRST (obj) = make_empty_list ();
  98.     DEQUELAST (obj) = make_empty_list ();
  99.     return (obj);
  100. }
  101.  
  102. Object
  103. make_deque_entry (Object prev, Object value, Object next)
  104. {
  105.     Object obj;
  106.  
  107.     obj = allocate_object (sizeof (struct deque_entry));
  108.  
  109.     DETYPE (obj) = DequeEntry;
  110.     DEPREV (obj) = prev;
  111.     DEVALUE (obj) = value;
  112.     DENEXT (obj) = next;
  113.     return (obj);
  114. }
  115.  
  116. Object
  117. make_deque_driver (Object args)
  118. {
  119.     int size;
  120.     Object size_obj, fill_obj, entry, first, last, deq;
  121.  
  122.     size = 0;
  123.     size_obj = NULL;
  124.     fill_obj = false_object;
  125.  
  126.     while (!NULLP (args)) {
  127.     if (FIRST (args) == size_keyword) {
  128.         size_obj = SECOND (args);
  129.     } else if (FIRST (args) == fill_keyword) {
  130.         fill_obj = SECOND (args);
  131.     } else {
  132.         error ("make: unsupported keyword for <deque> class",
  133.            FIRST (args), NULL);
  134.     }
  135.     args = CDR (CDR (args));
  136.     }
  137.     if (size_obj) {
  138.     if (!INTEGERP (size_obj)) {
  139.         error ("make: value of size: argument must be an integer",
  140.            size_obj, NULL);
  141.     }
  142.     size = INTVAL (size_obj);
  143.     }
  144.     deq = make_deque ();
  145.     /* actually fabricate the list representing the deque */
  146.     if (size--) {
  147.     first = last = make_deque_entry (make_empty_list (), fill_obj,
  148.                      make_empty_list ());
  149.     DEQUEFIRST (deq) = first;
  150.     while (size--) {
  151.         DENEXT (last) = make_deque_entry (last, fill_obj, NULL);
  152.         last = DENEXT (last);
  153.     }
  154.     DENEXT (last) = make_empty_list ();
  155.     DEQUELAST (deq) = last;
  156.     } else {
  157.     DEQUEFIRST (deq) = DEQUELAST (deq) =
  158.         DENEXT (deq) = make_empty_list ();
  159.     }
  160.     return (deq);
  161. }
  162.  
  163. /* primitives */
  164.  
  165. static Object
  166. push (Object d, Object new)
  167. {
  168.     Object new_entry;
  169.  
  170.     new_entry = make_deque_entry (make_empty_list (), new, DEQUEFIRST (d));
  171.     if (EMPTYLISTP (DEQUEFIRST (d))) {
  172.     DEQUEFIRST (d) = DEQUELAST (d) = new_entry;
  173.     } else {
  174.     DEPREV (DEQUEFIRST (d)) = new_entry;
  175.     DEQUEFIRST (d) = new_entry;
  176.     }
  177.     return (d);
  178. }
  179.  
  180. static Object
  181. pop (Object d)
  182. {
  183.     Object ret;
  184.  
  185.     if (EMPTYLISTP (DEQUEFIRST (d))) {
  186.     error ("pop: cannot pop empty <deque>", d, NULL);
  187.     }
  188.     ret = DEVALUE (DEQUEFIRST (d));
  189.     DEQUEFIRST (d) = DENEXT (DEQUEFIRST (d));
  190.     if (!EMPTYLISTP (DEQUEFIRST (d))) {
  191.     DEPREV (DEQUEFIRST (d)) = make_empty_list ();
  192.     }
  193.     return (ret);
  194. }
  195.  
  196. static Object
  197. push_last (Object d, Object new)
  198. {
  199.     Object new_entry;
  200.  
  201.     new_entry = make_deque_entry (DEQUELAST (d), new, make_empty_list ());
  202.     if (EMPTYLISTP (DEQUEFIRST (d))) {
  203.     DEQUEFIRST (d) = DEQUELAST (d) = new_entry;
  204.     } else {
  205.     DENEXT (DEQUELAST (d)) = new_entry;
  206.     DEPREV (new_entry) = DEQUELAST (d);
  207.     DEQUELAST (d) = new_entry;
  208.     }
  209.     return (d);
  210. }
  211.  
  212. static Object
  213. pop_last (Object d)
  214. {
  215.     Object res;
  216.  
  217.     if (EMPTYLISTP (DEQUEFIRST (d))) {
  218.     error ("pop-list: cannot pop empty <deque>", d, NULL);
  219.     }
  220.     res = DEVALUE (DEQUELAST (d));
  221.     if (DEQUEFIRST (d) == DEQUELAST (d)) {
  222.     DEQUEFIRST (d) = DEQUELAST (d) = make_empty_list ();
  223.     } else {
  224.     DEQUELAST (d) = DEPREV (DEQUELAST (d));
  225.     if (!EMPTYLISTP (DEQUELAST (d))) {
  226.         DENEXT (DEQUELAST (d)) = make_empty_list ();
  227.     }
  228.     }
  229.     return (res);
  230. }
  231.  
  232. static Object
  233. deque_first (Object d, Object default_ob)
  234. {
  235.     if (EMPTYLISTP (DEQUEFIRST (d))) {
  236.     if (default_ob == default_object) {
  237.         error ("first: empty <deque>", d, NULL);
  238.     } else {
  239.         return default_ob;
  240.     }
  241.     }
  242.     return (DEVALUE (DEQUEFIRST (d)));
  243. }
  244.  
  245. static Object
  246. deque_last (Object d, Object default_ob)
  247. {
  248.     if (EMPTYLISTP (DEQUELAST (d))) {
  249.     if (default_ob == default_object) {
  250.         error ("last: empty <deque>", d, NULL);
  251.     } else {
  252.         return default_ob;
  253.     }
  254.     }
  255.     return (DEVALUE (DEQUELAST (d)));
  256. }
  257.  
  258. static Object
  259. deque_element (Object d, Object index, Object default_ob)
  260. {
  261.     int i;
  262.     Object el;
  263.  
  264.     i = INTVAL (index);
  265.     el = DEQUEFIRST (d);
  266.     while (i) {
  267.     i--;
  268.     el = DENEXT (el);
  269.     if (EMPTYLISTP (el)) {
  270.         if (default_ob == default_object) {
  271.         error ("element: out of range", index, d, NULL);
  272.         } else {
  273.         return default_ob;
  274.         }
  275.     }
  276.     }
  277.     return (DEVALUE (el));
  278. }
  279.  
  280. static Object
  281. deque_element_setter (Object d, Object index, Object new)
  282. {
  283.     int i;
  284.     Object el;
  285.  
  286.     i = INTVAL (index);
  287.     el = DEQUEFIRST (d);
  288.     if (EMPTYLISTP (el)) {
  289.     error ("attempt to set element of empty deque", NULL);
  290.     }
  291.     while (i) {
  292.     i--;
  293.     el = DENEXT (el);
  294.     if (EMPTYLISTP (el)) {
  295.         error ("element: out of range", index, d, NULL);
  296.     }
  297.     }
  298.     DEVALUE (el) = new;
  299.     return (unspecified_object);
  300. }
  301.  
  302. static Object
  303. deque_initial_state (Object d)
  304. {
  305.     if (EMPTYLISTP (DEQUEFIRST (d))) {
  306.     return (false_object);
  307.     } else {
  308.     return (DEQUEFIRST (d));
  309.     }
  310. }
  311.  
  312. static Object
  313. deque_next_state (Object d, Object s)
  314. {
  315.     if (EMPTYLISTP (DENEXT (s))) {
  316.     return (false_object);
  317.     } else {
  318.     return (DENEXT (s));
  319.     }
  320. }
  321.  
  322. static Object
  323. deque_final_state (Object d)
  324. {
  325.     if (EMPTYLISTP (DEQUELAST (d))) {
  326.     return (false_object);
  327.     } else {
  328.     return (DEQUELAST (d));
  329.     }
  330. }
  331.  
  332. static Object
  333. deque_previous_state (Object d, Object s)
  334. {
  335.     if (EMPTYLISTP (DEPREV (s))) {
  336.     return (false_object);
  337.     } else {
  338.     return (DEPREV (s));
  339.     }
  340. }
  341.  
  342. static Object
  343. deque_current_element (Object d, Object s)
  344. {
  345.     return (DEVALUE (s));
  346. }
  347.  
  348. static Object
  349. deque_current_element_setter (Object d, Object s, Object new_value)
  350. {
  351.  
  352.     return (DEVALUE (s) = new_value);
  353. }
  354.